Search for: All records

We investigate the problem of designing randomized obviously strategyproof (OSP) mechanisms in several canonical auction settings. Obvious strategyproofness, introduced by Li [American Economic Review 2017], strengthens the well-known concept of dominant-strategy incentive compatibility (DSIC). Loosely speaking, it ensures that even agents who struggle with contingent reasoning can identify that their dominant strategy is optimal.Thus, one would hope to design OSP mechanisms with good approximation guarantees. Unfortunately, Ron [SODA 2024] has showed that deterministic OSP mechanisms fail to achieve an approximation better than the minimum of the number of items and the number of bidders, even for the simple settings of additive and unit-demand bidders. We circumvent these impossibilitiesby showing that randomized mechanisms that are obviously strategy-proof in the universal sense obtain a constant factor approximation for these classes. We show that this phenomenon occurs also for the setting of a multi-unit auction with single-minded bidders. Thus, our results provide a more positive outlook on the design of OSP mechanisms and exhibit a stark separation between the power of randomized and deterministic OSP mechanisms.To complement the picture, we provide lower bounds on the performance of randomized OSP mechanisms in each setting. This further demonstrates that OSP mechanisms are significantly weaker than dominant-strategy mechanisms: it is well known that the deterministic VCG mechanism outputs an optimal allocation in dominant-strategies, whereas we show that even randomized OSP mechanisms cannot obtain more than 87.5% of the optimal welfare. 

We study the communication complexity of dominant strategy implementations of combinatorial auctions. We start with two domains that are generally considered “easy”: multi-unit auctions with decreasing marginal values and combinatorial auctions with gross substitutes valuations. For both domains we have fast algorithms that find the welfare-maximizing allocation with communication complexity that is poly-logarithmic in the input size. This immediately implies that welfare maximization can be achieved in ex-post equilibrium with no significant communication cost, by using VCG payments. In contrast, we show that in both domains the communication complexity of any dominant strategy implementation that achieves the optimal welfare is polynomial in the input size. We then move on to studying the approximation ratios achievable by dominant strategy mechanisms. For multi-unit auctions with decreasing marginal values, we provide a dominant-strategy communication FPTAS. For combinatorial auctions with general valuations, we show that there is no dominant strategy mechanism that achieves an approximation ratio better than m1−є that uses poly(m,n) bits of communication, where m is the number of items and n is the number of bidders. In contrast, a randomized dominant strategy mechanism that achieves an O(√m) approximation with poly(m,n) communication is known. This proves the first gap between computationally efficient deterministic dominant strategy mechanisms and randomized ones. En route, we answer an open question on the communication cost of implementing dominant strategy mechanisms for more than two players, and also solve some open problems in the area of simultaneous combinatorial auctions.